package Graph;

import java.util.ArrayList;

public class Floyd {
    /**
     * @param matrix 邻接矩阵；不存在边连接时，值应设为Integer.MAX_VALUE；matrix[i][i]应设为0。
     * @return 三维数组array，array[0]是Floyd算法产生的距离矩阵dist，array[1]是Floyd算法产生的路径矩阵path；
     * 其中path[i][j]为-1可能表示：
     * (1) i->j的最短路径上已经不存在中间顶点
     * (2) i==j
     * (3) i不能到达j（此时dist[i][j]应为Integer.MAX_VALUE）
     * VERIFIED：初步测试证明实现正确。
     */
    public int[][][] solve(int[][] matrix) {
        int n = matrix.length;
        int[][] dist = new int[n][n];
        int[][] path = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = matrix[i][j];
                path[i][j] = -1; // path数组初始时全部设为-1
            }
        }

        // 核心代码：三重循环
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (j == i) continue;

                    if (dist[i][k] < Integer.MAX_VALUE && dist[k][j] < Integer.MAX_VALUE &&
                            dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = k;
                    }
                }
            }
        }

        // 浅拷贝
        int[][][] ret = new int[2][][];
        ret[0] = dist;
        ret[1] = path;
        return ret;
    }

    /**
     * 解析source到dest的路径。
     * VERIFIED：初步测试证明实现正确。
     */
    public ArrayList<Integer> parsePath(int[][] dist, int[][] path, int source, int dest) {
        ArrayList<Integer> ret = new ArrayList<>();
        int relay = path[source][dest];
        if (relay >= 0) {
            ArrayList<Integer> left = parsePath(dist, path, source, relay),
                    right = parsePath(dist, path, relay, dest);
            ret.addAll(left.subList(0, left.size() - 1)); // 去除重复顶点
            ret.addAll(right);
            return ret;
        }
        else { // relay == -1
            if (dist[source][dest] == Integer.MAX_VALUE) return null;
            else { // 直达
                ret.add(source);
                ret.add(dest);
                return ret;
            }
        }
    }

    public static void main(String[] args) {
        test();
    }

    private static void test() {
        final int INFINITY = Integer.MAX_VALUE;
        int[][] matrix = new int[][]{
                {0, 5, INFINITY, 7},
                {INFINITY, 0, 4, 2},
                {3, 3, 0, 2},
                {INFINITY, INFINITY, 1, 0}
        };

        Floyd solver = new Floyd();
        int[][][] floydResult = solver.solve(matrix);
        int[][] distMatrix = floydResult[0], pathMatrix = floydResult[1];

        ArrayList<Integer> path = solver.parsePath(distMatrix, pathMatrix, 1, 0);
        System.out.println(path);
    }
}
